package sword.offer;

/**
 * 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，
 * ……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
 *
 * 链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class FortySix {
    /**
     * 找出dp数组的含义  即dp[i]在数字的第i位的情况下的翻译方法数
     * 我们不难发现，当长度为1的时候 只有一种翻译方法  长度为2时 根据前一个数字和当前数字组合是否大于25来判断翻译次数。
     * 根据找出的规律：其中f(i)表示当数字长度为i时，有f(i)种翻译方法
     * 当组合数字不大于25时 f(i) = f(i-1) + f(i-2)
     * 当组合数字大于25时   f(i) = f(i-1)
     *
     * 要考虑到前一位数字是否为0
     *
     * 看了题解以后 大吃一惊，忘了字符串也能compare，所以转换成数字进行比较 没必要
     * */
    class Solution {
        public int translateNum(int num) {
            String s = String.valueOf(num);
            int[] dp = new int[s.length()];
            dp[0] = 1;
            if(s.length() <= 1){
                return 1;
            }
            if(((s.charAt(0) - '0') * 10 +  (s.charAt(1) - '0')) > 25){
                dp[1] = 1;
            }else{
                dp[1] = 2;
            }
            for (int i = 2; i < s.length(); i++) {
                int combinatorial = (s.charAt(i - 1) - '0') *10 + (s.charAt(i) - '0');
                if((s.charAt(i - 1) - '0') != 0 && combinatorial <= 25){
                    dp[i] = dp[i-1] + dp[i-2];
                }else{
                    dp[i] = dp[i-1];
                }
            }
            return dp[s.length()-1];
        }
    }
}
